package main

import (
	"fmt"
)

func RemoveDuplicateLetters(s string) string {
	stack := make([]byte, 0)
	// stack 用来快速判断，一个元素是否在栈中
	// sCnt 用来记录所有元素，当前遍历位置后面还有哪些元素
	stackCnt := make(map[byte]int, 0)
	sCnt := make(map[byte]int, 0)
	for i := 0; i < len(s); i++ {
		sCnt[s[i]] = sCnt[s[i]] + 1
	}
	for i := 0; i < len(s); i++ {
		// 遍历过的，从计数中删除，统计的是 遍历后还有哪些元素
		sCnt[s[i]] -= 1
		// 4. 如果当前元素已经在栈里面了，那就跳过。因为递增栈，删除开头的，那么只会导致字典序更大。
		if stackCnt[s[i]] > 0 {
			continue
		}
		// 1. 空栈直接添加， 或者当前元素大于栈顶 直接添加
		if len(stack) == 0 || s[i] > stack[len(stack)-1] {
			stackCnt[s[i]] = stackCnt[s[i]] + 1
			stack = append(stack, s[i])
			continue
		}
		fmt.Println(stack)
		// 2. 当前元素等于栈顶元素，啥也不干
		if s[i] == stack[len(stack)-1] {
			continue
		}
		// 3. 当前元素小于栈顶元素
		for len(stack) > 0 && s[i] < stack[len(stack)-1] {
			// 如果后面还有, 删除当前栈顶元素，否则退出
			c := stack[len(stack)-1]
			if sCnt[c] > 0 {
				stack = stack[:len(stack)-1]
				stackCnt[c] = stackCnt[c] - 1
			} else {
				break
			}
		}
		// 清除掉栈顶大于的元素（可能不需要清除），将当前元素添加进去
		stack = append(stack, s[i])
		stackCnt[s[i]] = stackCnt[s[i]] + 1
	}
	return string(stack)
}

func main() {
	//s := "cdadabcc"
	//rst := RemoveDuplicateLetters(s)
	//fmt.Println(rst)
	//c := 3
	//d := string(c)
	//fmt.Println(reflect.TypeOf(d))
	//a := '3'
	//e := "3"
	//fmt.Printf("%d", a)
	//fmt.Printf("%T", e)
	m := make(map[int]int)
	m[1235] = 2
	m[654764] = 3
	m[734542] = 4
	m[89938] = 5
	m[111234] = 6
	//for i := 0; i < 100; i++ {
	//	fmt.Println(m)
	//}

	//	map[1235:2 89938:5 654764:3 734542:4]
	//	map[1235:2 89938:5 654764:3 734542:4]
	//	map[1235:2 89938:5 654764:3 734542:4]
	type aa struct {
		a int
		*aa
	}
	var c = aa{1, nil}
	var d = aa{1, nil}
	var a = aa{3, &c}
	var b = aa{3, &d}
	fmt.Println(a == b)
	fmt.Println(a)
}
